BUBBLE SORTING Bubble sort is a routine designed to sort any number of elements in an array. The word 'BUBBLE' refers to the way in which each data item works its way up the list until it is in ascending or descending order. The algorithm for sorting an array is as follows: STEP 1. Examine the first two elements in the array STEP 2. If they are not in order then change (SWAP) them (Do nothing if they are in order). STEP 3. Go to the next pair of elements (EXAMPLE: If elements 1 & 2 were compared, next compare elements 2 & 3). STEP 4. Repeat STEP 2 and 3 until the last two elements in the array have been compared. At this point, the largest element in the list has 'BUBBLED' up the list so that it is now the last item in the list. STEP 5. Repeat the entire procedure for the first n-1 elements in the array (n is the total number of elements in the array). At this point the second largest element in the array will be second to last. Keep repeating this ( use n-2, n-3, n-4, ... n-[n-1]) until the entire array is sorted. The bubble sort technique requires approx. ½ * N² operations (N is the total number of elements in the array). As the array size increases, the sorting time increases greatly. A bubble sorting algorithm can be easily translated into any computer language code. The following page displays a bubble sorting program written in Quick BASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the Quick BASIC program listed on the next page: ARR$() = Array of type string used to store the data items. ARRAY.SIZE = Integer variable containing the size of the array. I = Integer index variable used showing the number of comparisons made during each pass. PASSES = Integer variable used in FOR-LOOP showing the total number of passes made in the array. REM Bubble sorting program: FOR passes = 1 TO array.size-1 ' STEPS 1. & 5. FOR i = 1 TO array.size - passes ' One less comparison each LOOP. IF arr$(i) > arr$(i + 1) THEN ' STEP 2. SWAP arr$(i), arr$(i+1) ' Swap if not in order. END IF NEXT i ' STEP 3. & 4. NEXT passes ' STEP 5. REM End of BUBBLE SORT The above screen displays the bubble sorting code that is used in the sorting process you are currently simulating. The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu. SHELL SORTING The shell sort (named after Donald L. Shell) is a variation of the insertion sort. When sorting large arrays, this sorting algorithm is much faster than the BUBBLE sort. The shell sort compares items that are a given number of elements away (usually INT(n/2)) and it will eventually compare items that are close together. If these items are out of their proper order, a swap is preformed. The following is the algorithm for the shell sort: STEP 1. Divide the array in half { gap = INT(n/2) } STEP 2. Compare the items in the 2 halves. (ie. 1st item with the first item in the second half). The next screen displays the order in which data is compared. STEP 1 STEP 2 (split in half) ( compare the halves ) ╔════════════════╗ ╔════════════════╗ ╔════════════════╗ ║ 1 ║ ║ 1 ║«SWAP?»║ 4 ║ ╟────────────────╢ ╟────────────────╢ ╟────────────────╢ ║ 2 ║ ║ 2 ║«SWAP?»║ 5 ║ ╟────────────────╢ ╟────────────────╢ ╟────────────────╢ ║ 3 ║ ║ 3 ║«SWAP?»║ 6 ║ -╟---------------─╢- ╚════════════════╝ ╚════════════════╝ ║ 4 ║ ╟────────────────╢ STEP 3. Keep comparing the elements in ║ 5 ║ STEP 2 until no more swaps can be ╟────────────────╢ made. ║ 6 ║ ╚════════════════╝ STEP 4. Divide the half into half again {gap = INT(gap/2)} STEP 5. Repeat steps 2, 3, and 4 until the GAP is zero. The shell sorting algorithm shown above may be written in the Quick BASIC program displayed on the next page. The following variables are utilized in the Shell sorting program: ARR$ = Array of type string used in storing the data items. ARRAY.SIZE = Integer used to define the number of data items. DONESWAPING = TRUE (1) / FALSE (0) Integer flag used to signal the end of swapping data items for this GAP. GAP = Integer used to define the range for comparing items. I = Integer variable used as an index pointer for ARR$. REM Shell sorting program: gap = INT(array.size / 2) ' STEP 1. Split the array in half DO WHILE gap >= 1 ' STEP 5. Do until gap = 0 DO doneSwaping = 1 ' Flag for NO MORE SWAPS. FOR i = 1 to array.size - gap ' STEP 2. Compare the halves IF arr$(i) > arr$(i + gap) THEN ' Swap these two elements. SWAP arr$(i) , arr$(i + gap) doneSwaping = 0 ' A swap was made, keep comparing END IF NEXT i LOOP UNTIL doneSwaping = 0 ' STEP 3. Keep comparing until NO ' MORE SWAPS can be made. gap = INT(gap / 2) ' STEP 4. Divide into half again. LOOP REM End of shell sorting program: The above screen displays the Shell sorting code that is used in the sorting process you are currently simulating. The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu. SHAKER SORTING The shaker sort ( sometimes referred to as the cocktail sorter ) is designed just like the BUBBLE sort except this algorithm utilizes aboolean (TRUE\FALSE) flag to indicate if the elements being compared are already in order. If they are in their proper place, then these elements are considered to be sorted. This improvement to the bubble sort may seem good, but it really makes little difference when sortinga large number elements (the number of exchanges are the same between the two). The shaker sort first moves the smallest item in the array to thetop and then it reverses direction and moves the largest item to the bottom of the array. Using this reversing method, the shaker sort canreduce the number of double checks that would be preformed in the BUBBLE sort. The following algorithm can be used for the shaker sort (Please refer to the BUBBLE SORT for more information): STEP 1. Preform another BUBBLE sorting pass in reverse order ( bottom to top ). At this point every item from the last SWAP upward is already in order and these items can be excluded from future comparisons. STEP 2. Preform a single BUBBLE SORT pass (top to bottom) on the array (Every item from the last SWAP down is sorted and should NOT be compared again). STEP 3. Keep comparing elements in steps 1 & 2 until no more elements are left to compare. The shaker sorting algorithm listed above can be easily translated into any computer language code. The following page displays a shaker sorting program written in Quick BASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the Quick BASIC program listed on the next page: ARR$() = Array of type string used to store the data items. ARRAY.SIZE = Integer variable containing the size of the array. I = Integer index variable used showing the number of comparisons made during each pass. TOP = Integer variable used to show the top sorting position in ARR$. BOTTOM = Integer variable used to show the last sorting position in ARR$. SORTED = Integer used to show the last swapping position. REM Shaker sorting program: top = 2 : bottom = array.size ' set top & bottom pointers. DO ' Part of step 3. FOR i = bottom TO top STEP -1 ' STEP 1. BUBBLE bottom to top. IF arr$[i-1] > arr$[i] THEN SWAP arr$[i-1] , arr$[i] sorted = i ' Records the last swap made. END IF NEXT i top = sorted + 1 ' Do not compare items from last ' SWAPPED item up. FOR i = top TO bottom ' STEP 2. BUBBLE top to bottom. IF arr$[i-1] > arr$[i] THEN SWAP arr$[i-1] , arr$[i] sorted = i ' Records the last swap made. END IF NEXT i bottom = sorted -1 ' Do not compare items from last ' SWAPPED item down. LOOP UNTIL top > bottom ' STEP 3. REM End of shaker SORT The above screen displays the bubble sorting code that is used in the sorting process you are currently simulating. The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu. QUICK SORTING Invented by C.A.R. Hoare, the Quick sort yields the best overall sorting method on arrays. Quick sorting is based on the principle that exchanges should be preformed over a large distance. For exampleif you had an array of size 100 and all of its elements are in reverseorder, it would be possible to sort the array in 50 exchanges. The Quick algorithm utilizes a PARTITION method which lends itself to RECURSION. Recursion is the use of a program that calls itself while it is being executed. The following algorithm can be used for the Quick Sort: STEP 1. Pick an array item at random (call it X). STEP 2. Scan the array, TOP - BOTTOM, until an item array(i) > X STEP 3. Scan the array, BOTTOM - TOP, until an item array(j) > X STEP 4. IF i <= J, exchange these items. STEP 5. Repeat STEPS 2 - 4 until the two scans meet ( i>j ). STEP 6. Apply the above method until the partitions created above consist only of a single item (RECURSION). The Quick sorting algorithm listed above can be easily translated into any computer language code. The following displays a Quick sorting program written in Quick BASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the Quick BASIC program listed on the next page: X$ = String variable used in the scan comparison. TOP = Upper integer position of the array. BOTTOM = Lower integer position of the array. I = Index for the TOP integer scan position. J = Index of the BOTTOM integer scan position. ARRAY$() = Array of type string that contains the unsorted data. SUB QuickSort(top,bottom,array$()) REM QUICK SORT PROGRAM: i = top: j = bottom X$ = array$(int((top+bottom)/2)) ' STEP 1 DO DO WHILE array$(i) < x$: i = i + 1: LOOP ' STEP 2 DO WHILE x$ < array$(j): j = j - 1: LOOP ' STEP 3 IF i < j THEN SWAP array$(i),array$(j) ' STEP 4 END IF IF i <= j THEN i = i + 1: j = j - 1 END IF LOOP UNTIL i > j ' STEP 5 IF top < j THEN ' STEP 6 CALL QuickSort(top, j, array$()) END IF IF i < bottom THEN CALL QuickSort(i,bottom,array$()) END IF END SUB The above Quick sorting program can also be written in a NON-RECURSIVE format. The following code is in Pascal format, but it can show how to encode a non-recursive Quick sort: Procedure NonRecursiveQuickSort; CONST M = 12; VAR i,j,L,R: index; x,w:item; s:[0..M]; stack: ARRAY[1..M] OF RECORD L,R: index END; BEGIN s:=1; stack[1].L:=1; stack[s].R:=n; REPEAT L:=stack[s].l; R:=stack[s].R; s:=s-1; REPEAT i:=L; j:=R; x:=a[(L+R) DIV 2]; REPEAT WHILE a[i] < x DO i:=i+1 END; WHILE x < a[j] DO j:=j-1 END; IF i <= j THEN w := a[i]; a[i] := a[j]; a[j] := w; i = i+1; j := j-1 END UNTIL i>j; IF i < R THEN s := s+1; stack[s].L := i; stack[s].R := R END; R := j UNTIL L >= R UNTIL s = 0 (* End of non-recursive quick sort *) The recursive QuickBASIC program above displays the Quick sort code that is used in the sorting process you are currently simulating.The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu. Linear Insertion Sort The linear or straight insertion sort is the simplest of the insertion algorithms to understand. The card playing method is a goodexample of how the linear insertion sort works. When a card player picks up a card from the deck, he (usually) starts from one end of hishand and inserts it in the proper sequence. The key to coding the linear insertion sort is the use of an array position of 0. This would permit the use of a sentinel technique that can be incorporated in the following algorithm: STEP 1. Move to next item (IF STARTING use item #2). STEP 2. Insert this item in the appropriate place in A1...Ai. STEP 3. If you're not at the last item, GO TO STEP 1. The Linear Insertion sorting algorithm listed above can be easily translated into any computer language code. The following displays a Linear Insertion sorting program written in QuickBASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the QuickBASIC program listed on the next page: ARRAY$() = Array of type string, used to store the data elements. I = Index variable used to refer to SORTED elements in ARRAY$ J = Index variable of ARRAY$() that is used for insertion of a new element between ARRAY$(1) ... ARRAY$(i). ARRAY.SIZE = Number of elements contained in ARRAY$(). REM Linear Insertion Sort: FOR i = 2 TO ARRAY.SIZE ' STEP 1. ARRAY$(0) = ARRAY$(i): j = i DO WHILE j >= 1 ' STEP 2. IF ARRAY$(0) < ARRAY$(j - 1) THEN SWAP ARRAY$(j), ARRAY$(j - 1) ELSE EXIT DO ' EXIT out of WHILE LOOP END IF j = j - 1 LOOP NEXT i ' STEP 3. REM End Of Linear Insertion Sort. The above screen displays the linear insertion sorting code that is used in the sorting process you are currently simulating. The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu. BINARY INSERTION SORTING The Binary Insertion Sort is an improvement over the linear because of the way which items are inserted into an array. When examining the linear insertion sort, you will notice that the data items from ARRAY$(1) to ARRAY$(i-1) are already sorted. The Binary Insertion Sort uses this feature to its advantage. This sorting process keeps halving the sorted array until a proper place is found to insert the item in question. When there are no more elements to insert, the array is sorted. The following algorithm describes the Binary Insertion sorting process: STEP 1. Move to next item -- X$ -- (IF STARTING use item #2). STEP 2. Divide the sorted elements in half (All of the items that you already looked at). If MIDDLE item is <= X$ divide TOP halve, otherwise, divide the BOTTOM half. STEP 3. Repeat STEP 2 until there is only one item. STEP 4. Insert X$ at this position. STEP 5. If X$ was not the last item, GOTO step 1. The Linear Insertion sorting algorithm listed above can be easily translated into any computer language code. The following displays a Linear Insertion sorting program written in QuickBASIC (Please remember that there are many different ways to translate any given algorithm). The following variables are used in the QuickBASIC program listed on the next page: ARRAY$() = Array of type string, used to store the data elements. X$ = String Item to be inserted. TOP = Array index for the upper position during division. BOTTOM = Array index for the lower position during division. MIDDLE = Mid point between TOP & BOTTOM. I = Array index variable used to scan entire array. ARRAY.SIZE = Total numbeer of items in array. J = Array index variable used to insert X$. REM Binary Insertion Sort: FOR i = 2 TO array.size ' STEP 1. X$ = array$(i): top = 1: bottom = i DO WHILE top < bottom ' STEP 3. middle = INT((top + bottom)/2) ' STEP 2. IF array$(middle) <= X$ THEN ' STEP 3. top = middle + 1 ELSE bottom = middle END IF LOOP ' STEP 2. FOR j = i TO bottom + 1 STEP - 1 ' STEP 4. array$(j) = array$(j-1) NEXT j array$(bottom) = X$ NEXT i ' STEP 5. The above screen displays the Binary Insertion sorting code that in the sorting process you are currently simulating. The array used for sorting data elements is located on the left side of the screen. Please remember to read the messages that are displayed at the bottom center of the screen. If you wish to speed up the simulation, press the ESC key to simulate at the fastest speed. For a graphical overview of this algorithm, select GRAPHICAL SORTING when you return to the Sub-Menu.
